from general_utilities import *
from monster_list import mlib
from object_list import olib
import os

class Grid_point:
  def __init__(self,down,right):
    self.down = down
    self.right = right

  def to_tuple(self):
    return ((self.down,self.right))         
    
  def point_in_dir(self,dir):
    result = Grid_point(self.down,self.right)
    if dir==DIR_UP:
      result.down = result.down-1
    elif dir==DIR_DOWN:
      result.down = result.down+1
    elif dir==DIR_RIGHT:
      result.right = result.right+1
    elif dir==DIR_LEFT:
      result.right = result.right-1
    elif dir==DIR_HERE:
      pass
    elif dir==DIR_NE:
      result.right = result.right+1      
      result.down = result.down-1    
    elif dir==DIR_NW:
      result.right = result.right-1      
      result.down = result.down-1    
    elif dir==DIR_SE:
      result.right = result.right+1      
      result.down = result.down+1    
    elif dir==DIR_SW:
      result.right = result.right-1      
      result.down = result.down+1    
    return result

  def __cmp__(self,other):
    if self.down == other.down and self.right == other.right:
      return 0
    elif self.down < other.down:
      return -1
    elif self.down > other.down:
      return 1
    elif self.right < other.right:
      return -1
    else:
      return 1

  def __repr__(self):
    return '(' + str(self.down) + " , " + str(self.right) + ")"

def subtract(grid_point_1,grid_point_2):
  return Grid_point(grid_point_1.down-grid_point_2.down,grid_point_1.right-grid_point_2.right)

def add(grid_point_1,grid_point_2):
  return Grid_point(grid_point_1.down+grid_point_2.down,grid_point_1.right+grid_point_2.right)
  
class Grid:
  def __init__(self,width,height,fill_with=None,definite_sockets=[],optional_sockets=[],sep='',show_border='#',show_definite_socket='+',show_optional_socket='O'):
    self.width = width
    self.height = height
    self.sep = sep # used when printing
    self.show_border = show_border # ditto
    self.show_definite_socket = show_definite_socket # ditto
    self.show_optional_socket = show_optional_socket # ditto
    self.sockets = definite_sockets+optional_sockets # vector of Grid_points around the outside
    self.sockets_optional = [0]*len(definite_sockets)+[1]*len(optional_sockets)
    # we'll just check the sockets
    for socket in self.sockets:
      if not (socket.down==-1 or socket.down==self.height or socket.right==-1 or socket.right==self.width):
        print "Bad sockets!"
        raise SystemError
    self.g = [] # indexed by down, right
    for i in range(self.height):
      row = []
      for j in range(self.width):
        row.append(fill_with)       
      self.g.append(row)
  
  def get_cell(self,grid_point):
    return self.g[grid_point.down][grid_point.right]

  def set_cell(self,grid_point,value):
    self.g[grid_point.down][grid_point.right] = value

  def add_definite_socket(self,grid_point):
    # no checks
    self.sockets.append(grid_point)
    self.sockets_optional.append(0)
  
  def has_any(self,entries):
    for i in range(self.height):
      for j in range(self.width):
        if self.g[i][j] in entries:
          return 1
    return 0

  def lrflip(self):
    for i in range(self.height):
      self.g[i].reverse()
    for j in range(len(self.sockets)):
      self.sockets[j].right = self.width-self.sockets[j].right-1
    return self
      
  def udflip(self):
    for i in range(self.height/2):
      temp = self.g[i]
      self.g[i] = self.g[self.height-1-i]
      self.g[self.height-1-i] = temp
    for j in range(len(self.sockets)):
      self.sockets[j].down = self.height-self.sockets[j].down-1
    return self

  def rotate_clockwise(self,quadrants):
    if quadrants%4==0:
      pass
    else:
      new_grid = Grid(self.width,self.height)
      new_grid.blit(self,Grid_point(0,0),quadrants)
      self.g = new_grid.g 
      for j in range(len(self.sockets)):
        self.sockets[j] = self.rotate_point_clockwise(self.sockets[j],quadrants)

  def socket_is_optional(self,socket):
    for i in range(len(self.sockets)):
      if self.sockets[i]==socket:
        return self.sockets_optional[i]
      
  def __repr__(self):
    result = ""
    if self.show_border<>'':
      for j in range(-1,self.width+1):
        if Grid_point(-1,j) in self.sockets:
          if self.socket_is_optional(Grid_point(-1,j)):
            result = result + self.show_optional_socket + self.sep
          else:
            result = result + self.show_definite_socket + self.sep
        else:
          result = result + self.show_border + self.sep
      result = result+'\n'
    for i in range(self.height):
      if self.show_border<>'':
        if Grid_point(i,-1) in self.sockets:
          if self.socket_is_optional(Grid_point(i,-1)):
            result = result + self.show_optional_socket + self.sep
          else:
            result = result + self.show_definite_socket + self.sep
        else:
          result = result + self.show_border + self.sep
      for j in range(self.width):
        result = result + str(self.g[i][j]) + self.sep
      if self.show_border<>'':
        if Grid_point(i,self.width) in self.sockets:
          if self.socket_is_optional(Grid_point(i,self.width)):
            result = result + self.show_optional_socket + self.sep
          else:
            result = result + self.show_definite_socket + self.sep
        else:
          result = result + self.show_border + self.sep
      result = result+'\n'
    if self.show_border<>'':
      for j in range(-1,self.width+1):
        if Grid_point(self.height,j) in self.sockets:
          if self.socket_is_optional(Grid_point(self.height,j)):
            result = result + self.show_optional_socket + self.sep
          else:
            result = result + self.show_definite_socket + self.sep
        else:
          result = result + self.show_border + self.sep
      result = result+'\n'
    return result      
  
  def blit(self,other,top_left,quadrants_clockwise=0,convert={}):
    for i in range(other.height):
      for j in range(other.width):
        if quadrants_clockwise%4==0:
          self_i = top_left.down+i
          self_j = top_left.right+j
        elif quadrants_clockwise%4==1:
          self_i = top_left.down+j
          self_j = top_left.right+(other.height-i-1)
        elif quadrants_clockwise%4==2:
          self_i = top_left.down+(other.height-i-1)
          self_j = top_left.right+(other.width-j-1)
        elif quadrants_clockwise%4==3:
          self_i = top_left.down+(other.width-j-1)
          self_j = top_left.right+i
        if self_i>=0 and self_i<self.height and self_j>=0 and self_j<self.width:
          to = other.g[i][j]
          self.g[self_i][self_j] = convert.get(to,to)

  def stipple_with_blocks(self,proportion,wall_type='#',floor_type='.'):
    # maintains guaranteed connectivity without pathfinding
    # proportion is an upper_bound not an expectation
    self.fill(floor_type)
    for count in range(floor(self.height*self.width*proportion)):
      i = random.randint(1,self.height-2)
      j = random.randint(1,self.width-2)
      point = Grid_point(i,j)
      ok = 1
      for ii in range(i-1,i+2):
        for jj in range(j-1,j+2):
          if self.get_cell(Grid_point(ii,jj))<>floor_type:
            ok = 0
            break
        if ok == 0:
          break
      if ok:
        self.set_cell(point,wall_type)

  def fill_with_maze(self,straightness,horizontalness,forkiness,wall_type='#',floor_type='.'):
    # 1 is very straight, -1 very jumbly
    # -1 or 1 is very one-directional, 0 can go either way
    # 0 is not at all forky, 0.5 is quite overconnected
    self.clear()
    filled = 0
    # We need an odd-dimensioned area, if either dimension is even then add a line of wall to make it odd
    if self.width%2==0:
      for i in range(0,self.height):
        self.g[i][0] = wall_type
      new_grid = Grid(self.width-1,self.height)
      new_start = Grid_point(0,1)
      new_grid.fill_with_maze(straightness,horizontalness,forkiness)
      self.blit(new_grid,new_start)
      filled = 1
    if not filled and self.height%2==0:
      for j in range(0,self.width):
        self.g[0][j] = wall_type
      new_grid = Grid(self.width,self.height-1)
      new_start = Grid_point(1,0)
      new_grid.fill_with_maze(straightness,horizontalness,forkiness)
      self.blit(new_grid,new_start)
      filled = 1   
    if not filled:
      # make the maze
      # first set up the grid of rooms
      self.fill(wall_type)
      rooms_height = (self.height+1)/2
      rooms_width = (self.width+1)/2
      for i in range(0,rooms_height):
        for j in range(0,rooms_width):
          self.g[i*2][j*2] = floor_type
      # then connect rooms
      room_to_tunnel_from = [random.randint(0,rooms_height-1),random.randint(0,rooms_width-1)]
      rooms_visited = [room_to_tunnel_from]
      n_rooms = rooms_height*rooms_width
      last_dir_to_tunnel_in = None
      while (len(rooms_visited)<n_rooms):
        stuck = 0
        while (not stuck):
          # attempt to tunnel from here
          dirs = [DIR_UP,DIR_DOWN,DIR_RIGHT,DIR_LEFT]
          dir_prefs = []
          max_pref = 0
          for dir in dirs:
            dir_prefs.append(0)
            pref = 1
            if room_to_tunnel_from[0]==0 and dir==DIR_UP:
              continue
            elif room_to_tunnel_from[0]==rooms_height-1 and dir==DIR_DOWN:
              continue
            elif room_to_tunnel_from[1]==0 and dir==DIR_LEFT:
              continue
            elif room_to_tunnel_from[1]==rooms_width-1 and dir==DIR_RIGHT:
              continue
            room_would_be_next = [room_to_tunnel_from[0],room_to_tunnel_from[1]]
            if dir==DIR_UP:
              room_would_be_next[0] = room_would_be_next[0]-1
            elif dir==DIR_DOWN:
              room_would_be_next[0] = room_would_be_next[0]+1
            elif dir==DIR_RIGHT:
              room_would_be_next[1] = room_would_be_next[1]+1
            elif dir==DIR_LEFT:
              room_would_be_next[1] = room_would_be_next[1]-1
            if room_would_be_next in rooms_visited:
              continue
            if last_dir_to_tunnel_in is not None:
              if opposite(dir)==last_dir_to_tunnel_in:
                continue
              elif dir<>last_dir_to_tunnel_in:
                pref = pref * (1.01 - straightness)
            if (dir==DIR_RIGHT or dir==DIR_LEFT) and horizontalness < 0:
              pref = pref * (1.01 + horizontalness)
            elif (dir==DIR_UP or dir==DIR_DOWN) and horizontalness > 0:
              pref = pref * (1.01 - horizontalness)  
            dir_prefs[len(dir_prefs)-1] = pref
            max_pref = max(max_pref,pref)
          if max_pref==0:
            stuck = 1
            continue
          dir_probs = []
          for i in range(len(dirs)):
            dir_probs.append(dir_prefs[i]/max_pref)
          while (1):
            i = random.randint(0,3)
            if random.random()<dir_probs[i]:
              dir_to_tunnel_in = dirs[i]
              break
          if dir_to_tunnel_in==DIR_UP:
            grid_to_dig_out = Grid_point(room_to_tunnel_from[0]*2-1,room_to_tunnel_from[1]*2)
            new_room = [room_to_tunnel_from[0]-1,room_to_tunnel_from[1]]
          elif dir_to_tunnel_in==DIR_DOWN:
            grid_to_dig_out = Grid_point(room_to_tunnel_from[0]*2+1,room_to_tunnel_from[1]*2)
            new_room = [room_to_tunnel_from[0]+1,room_to_tunnel_from[1]]
          elif dir_to_tunnel_in==DIR_RIGHT:
            grid_to_dig_out = Grid_point(room_to_tunnel_from[0]*2,room_to_tunnel_from[1]*2+1)
            new_room = [room_to_tunnel_from[0],room_to_tunnel_from[1]+1]
          elif dir_to_tunnel_in==DIR_LEFT:
            grid_to_dig_out = Grid_point(room_to_tunnel_from[0]*2,room_to_tunnel_from[1]*2-1)
            new_room = [room_to_tunnel_from[0],room_to_tunnel_from[1]-1]
          else: 
            stuck = 1
          if not self.valid(grid_to_dig_out):
            stuck = 1
          if not stuck:
            self.set_cell(grid_to_dig_out,floor_type)
          rooms_visited.append(new_room)
          room_to_tunnel_from = new_room
          last_dir_to_tunnel_in = dir_to_tunnel_in
        room_to_tunnel_from = rooms_visited[random.randint(0,len(rooms_visited)-1)]
        last_dir_to_tunnel_in = None
      # then add extra connections
      for count in range(0,int(n_rooms*forkiness)):
        room_to_tunnel_from = [random.randint(0,rooms_height-1),random.randint(0,rooms_width-1)]
        dir_to_tunnel_in = [DIR_UP,DIR_DOWN,DIR_RIGHT,DIR_LEFT][random.randint(0,3)]
        if dir_to_tunnel_in==DIR_UP:
          grid_to_dig_out = Grid_point(room_to_tunnel_from[0]*2-1,room_to_tunnel_from[1]*2)
        elif dir_to_tunnel_in==DIR_DOWN:
          grid_to_dig_out = Grid_point(room_to_tunnel_from[0]*2+1,room_to_tunnel_from[1]*2)
        elif dir_to_tunnel_in==DIR_RIGHT:
          grid_to_dig_out = Grid_point(room_to_tunnel_from[0]*2,room_to_tunnel_from[1]*2+1)
        elif dir_to_tunnel_in==DIR_LEFT:
          grid_to_dig_out = Grid_point(room_to_tunnel_from[0]*2,room_to_tunnel_from[1]*2-1)
        if self.valid(grid_to_dig_out):
          self.set_cell(grid_to_dig_out,floor_type)
      # done mazing
      filled = 1
    # bore in from the sockets
    for socket in self.sockets:
      dir_inwards = self.dir_into_grid(socket)
      pos_to_empty = socket.point_in_dir(dir_inwards)
      while self.get_cell(pos_to_empty)<>floor_type:
        self.set_cell(pos_to_empty,floor_type)
        adjacent_to_whitespace = 0
        for adjacent_dir in [DIR_UP,DIR_DOWN,DIR_RIGHT,DIR_LEFT]:
          if opposite(adjacent_dir)<>dir_inwards:
            point_to_check = pos_to_empty.point_in_dir(adjacent_dir)
            if point_to_check.down>=0 and point_to_check.right>=0 and point_to_check.down<self.height and point_to_check.right<self.width:
              if self.get_cell(point_to_check)==floor_type:
                adjacent_to_whitespace = 1
        if adjacent_to_whitespace:
          break
        pos_to_empty = pos_to_empty.point_in_dir(dir_inwards)
    
  def dir_into_grid(self,socket):
    # e.g. if off the top, return down
    if socket.down < 0:
      return DIR_DOWN
    elif socket.down >= self.height:
      return DIR_UP
    elif socket.right < 0:
      return DIR_RIGHT
    elif socket.right >= self.width:
      return DIR_LEFT
    else:
      return DIR_HERE
    
  def clear(self):
    self.fill(None)
  
  def fill(self,with):
    for i in range(self.height):
      for j in range(self.width):
        self.g[i][j] = with
        
  def valid(self,point):
    if point.down>=0 and point.down<self.height and point.right>=0 and point.right<self.width:
      return 1
    return 0
  
  def rotate_point_clockwise(self,point,quadrants):
    if quadrants%4==0:
      return Grid_point(point.down,point.right)
    elif quadrants%4==1:
      return Grid_point(point.right,self.height-point.down-1)
    elif quadrants%4==2:
      return Grid_point(self.height-point.down-1,self.width-point.right-1)
    elif quadrants%4==3:
      return Grid_point(self.width-point.right-1,point.down)    

  def read_bordered_grid(self,buffer,definite_socket_chars,optional_socket_chars):
    # buffer is a [string]
    # socket_chars a [char]
    # Assume dimensions are correct (needs to be done by higher level function)
    self.sockets = []
    self.sockets_optional = []
    for i in range(-1,self.height+1):
      if buffer[i+1][0] in definite_socket_chars:
        self.sockets.append(Grid_point(i,-1))
        self.sockets_optional.append(0)
      elif buffer[i+1][0] in optional_socket_chars:
        self.sockets.append(Grid_point(i,-1))
        self.sockets_optional.append(1)
      if buffer[i+1][self.width+1] in definite_socket_chars:
        self.sockets.append(Grid_point(i,self.width))  
        self.sockets_optional.append(0)
      elif buffer[i+1][self.width+1] in optional_socket_chars:
        self.sockets.append(Grid_point(i,self.width))  
        self.sockets_optional.append(1)
    for j in range(-1,self.width+1):
      if buffer[0][j+1] in definite_socket_chars:
        self.sockets.append(Grid_point(-1,j))
        self.sockets_optional.append(0)
      elif buffer[0][j+1] in optional_socket_chars:
        self.sockets.append(Grid_point(-1,j))
        self.sockets_optional.append(1)
      if buffer[self.height+1][j+1] in definite_socket_chars:
        self.sockets.append(Grid_point(self.height,j))   
        self.sockets_optional.append(0)
      elif buffer[self.height+1][j+1] in optional_socket_chars:
        self.sockets.append(Grid_point(self.height,j))   
        self.sockets_optional.append(1)
    for i in range(0,self.height):    
      for j in range(0,self.width):
        self.g[i][j] = buffer[i+1][j+1]
 
def load_bordered_grids(filename,definite_socket_chars=['+'],optional_socket_chars=['O']):
  # return a [Grid]
  file = open(filename,'r')
  lines = file.readlines()
  i = 0
  buffer = []
  results = []
  while i<len(lines):
    if lines[i].strip()=='':
      if len(buffer)>0:
        grid = Grid(len(buffer[0])-2,len(buffer)-2)
        grid.read_bordered_grid(buffer,definite_socket_chars=definite_socket_chars,optional_socket_chars=optional_socket_chars)
        results.append(grid)
        buffer = []
      i=i+1
      continue
    buffer.append(lines[i].strip())
    i=i+1
  if len(buffer)>0:
    grid = Grid(len(buffer[0])-2,len(buffer)-2)
    grid.read_bordered_grid(buffer,definite_socket_chars=definite_socket_chars,optional_socket_chars=optional_socket_chars)
    results.append(grid)
  file.close()
  return results

TP_NO_INTERIOR_WALLS = 0 # switch
TP_PARENT_WALL_TYPE = 3 # W_ code
TP_PARENT_FLOOR_TYPE = 4 # F_ code
TP_ORGANIC = 5 # switch
TP_CONVERT = 6 # {} from char to char
TP_WET = 7 # switch
TP_FIERY = 8 # switch
TP_IS_ENCOUNTER = 9 # switch
TP_IS_GOOD_ENCOUNTER = 10 # switch
TP_THEMES = 11 # list of [E_ code], for encounters
TP_CLASSIC = 12 # switch
TP_OPEN = 13 # switch
TP_MAZY = 14 # switch
TP_CORRIDOR = 14.5 # switch
TP_NO_ORGANIC_SUBAREAS = 20 # switch
TP_WANT_ENCOUNTER = 21 # switch
TP_NO_ENCOUNTER = 22 # switch
TP_WANT_GOOD_ENCOUNTER = 23 # switch
TP_NEVER_ROTATE = 41 # switch
# Everything from here down could potentially be used at the Ready_level level
# Control look
TP_WALL_TYPE = 1 # W_ code
TP_FLOOR_TYPE = 2 # F_ code
# Control template selection
TP_ORGANIC_PROB = 24 # float multiplier
TP_NON_ORGANIC_PROB = 25 # float multiplier
TP_WET_PROB = 26 # float multiplier
TP_NON_WET_PROB = 27 # float multiplier
TP_FIERY_PROB = 28 # float multiplier
TP_NON_FIERY_PROB = 29 # float multiplier
TP_CLASSIC_PROB = 30 # float multiplier
TP_NON_CLASSIC_PROB = 31 # float multiplier
TP_OPEN_PROB = 32 # float multiplier
TP_NON_OPEN_PROB = 33 # float multiplier
TP_MAZY_PROB = 34 # float multiplier
TP_NON_MAZY_PROB = 35 # float multiplier
TP_CORRIDOR_PROB = 50 # float multiplier
TP_NON_CORRIDOR_PROB = 51 # float multiplier
# Control random object and monster probabilities
TP_LOOT_CHANCE = 46 # prob of each additional loot item, usually about 0.4, never very high or crash
TP_RANDOM_MONSTER_CHANCE = 47 # prob of trying for a monster, this can be 1
# Control monster types
TP_THEME_PROBS = 36 # dict (prob incomplete) from E_ code to float multiplier
# Control monster and object types
TP_LEVEL_DIFFICULTY = 40 # int
# Control random object types
TP_ALLOWED_SLOTS = 42 # Either this and TP_ALLOWED_ITEMS are None, or this is [SL_ code]
TP_ALLOWED_ITEMS = 43 # Either this and TP_ALLOWED_SLOTS are None, or this is [O_ code] 
# Control terrain types and probabilities
TP_TERRAIN_CHANCE = 44 # prob of unusual terrain, usually about 0.4, but will need to rise if the below used extensively
TP_TERRAIN_VETO_PROBS = 45 # dict from terrain char (e.g. '*') to veto probability (if omitted, no veto applied) - only used when building encounters. Can be of ('!','*',')','(','?','^','3','8','@','7','9',':','&','!') so far. Note '!' is often placed with a template anyway.

class Template(Grid):
  def __init__(self,raw_grid,use_prob=0.3,level=1,lowercase_letters={},ambient_messages=[],inheritable_properties={},child_only_properties={},self_only_properties={},entrance=0,include_outer_walls=0,keys_required_somewhere=[]):
    self.count = 0
    buffer = text_block_to_list_of_strings(raw_grid)
    Grid.__init__(self,len(buffer[0])-2,len(buffer)-2,show_border='')
    if not (len(buffer)==25 and len(buffer[0])==25): # usually
      self.read_bordered_grid(buffer,['+'],['O'])
    else: # for preset rooms
      self.read_bordered_grid(buffer,[],[])
      self.exit_types = {} # for preset rooms only: DIR_ code to char
      self.exit_types[DIR_UP] = buffer[1][12]
      self.exit_types[DIR_DOWN] = buffer[23][12]
      self.exit_types[DIR_LEFT] = buffer[12][1]
      self.exit_types[DIR_RIGHT] = buffer[12][23]
      for dir in [DIR_UP,DIR_LEFT,DIR_DOWN,DIR_RIGHT]:
        if self.exit_types[dir]=='~':
          self.exit_types[dir]='#'
      self.entrance = entrance 
    self.keys_required_somewhere = keys_required_somewhere # [char] - e.g. ['$']
    self.has_interior_walls = self.has_any(['#','X','M'])
    self.use_prob = use_prob # on [0,1]
    self.level = level # int
    self.ambient_messages = ambient_messages # [string]
    self.inheritable_properties = {} # {TP_ code, anything}
    self.child_only_properties = {} # {TP_ code, anything}
    self.self_only_properties = {} # {TP_ code, anything}
    self.lowercase_letters = lowercase_letters # {char, Special_grid}
    for key in inheritable_properties.keys():
      self.inheritable_properties[key] = inheritable_properties[key] 
    for key in child_only_properties.keys():
      self.child_only_properties[key] = child_only_properties[key] 
    for key in self_only_properties.keys():
      self.self_only_properties[key] = self_only_properties[key] 
    #if random.random()<0.5:
      #self.child_only_properties[TP_NO_INTERIOR_WALLS] = 1
    #else:
      #self.self_only_properties[TP_FLOOR_TYPE] = F_COBBLES_DARK
      
  def apply(self,ready_room,subgrid,offset,rotation,inherited_properties):
    # return a {TP_ code, anything} of child properties
    self.count = self.count + 1
    convert = self.get_property(TP_CONVERT,{},inherited_properties)
    difficulty = self.get_property(TP_LEVEL_DIFFICULTY,{},inherited_properties)
    allowed_slots = self.get_property(TP_ALLOWED_SLOTS,None,inherited_properties)
    allowed_items = self.get_property(TP_ALLOWED_ITEMS,None,inherited_properties)
    subgrid.blit(self,Grid_point(0,0),rotation,convert=convert)
    group = Ready_group()
    group.attitude = A_HOSTILE
    group.monster_types = []
    group.locations = []
    if len(self.lowercase_letters):
      for i in range(subgrid.height):
        for j in range(subgrid.width):
          character = subgrid.g[i][j]
          if character>='a' and character<='z':
            self.convert_lowercase_letter(ready_room,subgrid,offset,Grid_point(i,j),convert,group,difficulty,allowed_slots,allowed_items)
    this_wall_type = self.get_property(TP_WALL_TYPE,ready_room.main_wall_type,inherited_properties)
    parent_wall_type = self.get_property(TP_PARENT_WALL_TYPE,ready_room.main_wall_type,inherited_properties)
    if this_wall_type<>parent_wall_type:
      ready_room.multi_wall_types = 1
      for i in range(subgrid.height):
        for j in range(subgrid.width):
          ready_room.other_wall_types[(i+offset.down,j+offset.right)] = this_wall_type
    this_floor_type = self.get_property(TP_FLOOR_TYPE,ready_room.main_floor_type,inherited_properties)
    parent_floor_type = self.get_property(TP_PARENT_FLOOR_TYPE,ready_room.main_floor_type,inherited_properties)
    if this_floor_type<>parent_floor_type:
      for i in range(subgrid.height):
        for j in range(subgrid.width):
          ready_room.other_floor_types[(i+offset.down,j+offset.right)] = this_floor_type
    ready_room.ambient_messages = ready_room.ambient_messages + self.get_ambient_messages()
    if self.get_property(TP_NO_ENCOUNTER,0,inherited_properties):
      good_encounter_prob = 0
      encounter_prob = 0
    elif self.get_property(TP_IS_ENCOUNTER,0,inherited_properties) or self.get_property(TP_IS_GOOD_ENCOUNTER,0,inherited_properties):
      good_encounter_prob = 0
      encounter_prob = 0
    elif self.get_property(TP_WANT_ENCOUNTER,0,inherited_properties):
      good_encounter_prob = 0.1
      encounter_prob = 0.8
    elif self.get_property(TP_WANT_GOOD_ENCOUNTER,0,inherited_properties):
      good_encounter_prob = 0.7
      encounter_prob = 0.95   
    else:
      good_encounter_prob = min(0.1,0.002*subgrid.height*subgrid.height)
      encounter_prob = min(0.7,0.01*subgrid.height*subgrid.width)     
    if random.random()<good_encounter_prob:
      place_encounter(self,inherited_properties,ready_room,subgrid,offset,group,good=1,no_monsters=0)
    elif random.random()<encounter_prob:
      place_encounter(self,inherited_properties,ready_room,subgrid,offset,group,good=0,no_monsters=0)
    if len(group.monster_types)>0:
      ready_room.groups.append(group)
    child_properties = {}
    for key in inherited_properties.keys():
      child_properties[key] = inherited_properties[key]
    for key in self.inheritable_properties.keys():
      child_properties[key] = self.inheritable_properties[key]
    for key in self.child_only_properties.keys():
      child_properties[key] = self.child_only_properties[key]
    child_properties[TP_PARENT_FLOOR_TYPE] = this_floor_type
    child_properties[TP_PARENT_WALL_TYPE] = this_wall_type
    return child_properties
  
  def convert_lowercase_letter(self,ready_room,subgrid,offset,subgrid_point,convert,group,difficulty,allowed_slots,allowed_items):
    char = subgrid.get_cell(subgrid_point)
    translation = self.lowercase_letters[char]
    subgrid.set_cell(subgrid_point,convert.get(translation.terrain,translation.terrain))
    offset_location = (subgrid_point.down+offset.down,subgrid_point.right+offset.right)
    if translation.signpost_message is not None:
      ready_room.signpost_messages[offset_location] = translation.signpost_message 
    if translation.exit_to is not None:
      ready_room.exits_to[offset_location] = translation.exit_to
    elif translation.terrain=='}':
      ready_room.exits_to[offset_location] = (D_TBC,-1)
    if random.random() < translation.monster_probability:
      if translation.monster is not None:
        group.monster_types.append(translation.monster)
        group.locations.append(offset_location)
    if random.random() < translation.object_probability:
      possible_objects,possible_object_probs,possible_good_objects,possible_good_object_probs = get_object_tables(difficulty,allowed_slots,allowed_items)
      if translation.random_good_object:
        if len(possible_good_objects)>0:
          for i in range(10):
            j = random.randint(0,len(possible_good_objects)-1)
            chosen_object = possible_good_objects[j]
            if random.random()<possible_good_object_probs[j]:   
              ready_room.objects[offset_location] = chosen_object
              break
      elif translation.random_object:
        if len(possible_objects)>0:
          for i in range(10):
            j = random.randint(0,len(possible_objects)-1)
            chosen_object = possible_objects[j]
            if random.random()<possible_object_probs[j]:        
              ready_room.objects[offset_location] = chosen_object
              break
      elif translation.object is not None:
        ready_room.objects[offset_location] = translation.object 
     
  def get_property(self,key,default,inherited_properties):
    if key in inherited_properties.keys():
      return inherited_properties[key]
    if key in self.inheritable_properties.keys():
      return self.inheritable_properties[key]
    if key in self.self_only_properties.keys():
      return self.self_only_properties[key]
    return default
  
  def get_ambient_messages(self):
    return self.ambient_messages
  
  def prob_to_insert(self,properties_from_parent,rotation):
    if properties_from_parent.get(TP_NO_INTERIOR_WALLS,0) and self.has_interior_walls:
      return 0
    elif properties_from_parent.get(TP_NO_ORGANIC_SUBAREAS,0) and self.get_property(TP_ORGANIC,0,{}):
      return 0
    elif properties_from_parent.get(TP_NO_ENCOUNTER,0) and (self.get_property(TP_IS_ENCOUNTER,0,{}) or self.get_property(TP_IS_GOOD_ENCOUNTER,0,{})):
      return 0
    elif rotation<>0 and self.get_property(TP_NEVER_ROTATE,0,{}):
      return 0
    else:
      template = 0
      prob = self.use_prob
      if self.get_property(TP_IS_ENCOUNTER,0,{}) or self.get_property(TP_IS_GOOD_ENCOUNTER,0,{}):
        out_of_depth = self.level-self.get_property(TP_LEVEL_DIFFICULTY,1,properties_from_parent)
        template = 1 
        if out_of_depth>=3:
          return 0
        elif out_of_depth>0:
          prob = prob * pow(0.5,out_of_depth)
      classic_prob_mult = properties_from_parent.get(TP_CLASSIC_PROB,1)
      non_classic_prob_mult = properties_from_parent.get(TP_NON_CLASSIC_PROB,1)
      organic_prob_mult = properties_from_parent.get(TP_ORGANIC_PROB,1)
      non_organic_prob_mult = properties_from_parent.get(TP_NON_ORGANIC_PROB,1)
      wet_prob_mult = properties_from_parent.get(TP_WET_PROB,1)
      non_wet_prob_mult = properties_from_parent.get(TP_NON_WET_PROB,1)
      fiery_prob_mult = properties_from_parent.get(TP_FIERY_PROB,1)
      non_fiery_prob_mult = properties_from_parent.get(TP_NON_FIERY_PROB,1)
      open_prob_mult = properties_from_parent.get(TP_OPEN_PROB,1)
      non_open_prob_mult = properties_from_parent.get(TP_NON_OPEN_PROB,1)
      mazy_prob_mult = properties_from_parent.get(TP_MAZY_PROB,1)
      non_mazy_prob_mult = properties_from_parent.get(TP_NON_MAZY_PROB,1)
      corridor_prob_mult = properties_from_parent.get(TP_CORRIDOR_PROB,1)
      non_corridor_prob_mult = properties_from_parent.get(TP_NON_CORRIDOR_PROB,1)
      if self.get_property(TP_CLASSIC,0,{}):
        prob = prob * classic_prob_mult
      else:
        prob = prob * non_classic_prob_mult
      if self.get_property(TP_ORGANIC,0,{}):
        prob = prob * organic_prob_mult
      else:
        prob = prob * non_organic_prob_mult
      if self.get_property(TP_OPEN,0,{}):
        prob = prob * open_prob_mult
      else:
        prob = prob * non_open_prob_mult
      if self.get_property(TP_CORRIDOR,0,{}):
        prob = prob * corridor_prob_mult
      else:
        prob = prob * non_corridor_prob_mult
      if self.get_property(TP_MAZY,0,{}):
        prob = prob * mazy_prob_mult
      else:
        prob = prob * non_mazy_prob_mult
      if self.get_property(TP_WET,0,{}) or properties_from_parent.get(TP_CONVERT,{}).get('#','#')=='~':
        prob = prob * wet_prob_mult
      else:
        prob = prob * non_wet_prob_mult
      if self.get_property(TP_FIERY,0,{}) or properties_from_parent.get(TP_CONVERT,{}).get('#','#')=='*':
        prob = prob * fiery_prob_mult
      else:
        prob = prob * non_fiery_prob_mult
      if prob==0:
        return 0
      theme_prob_mults = properties_from_parent.get(TP_THEME_PROBS,None)
      if theme_prob_mults is not None:
        encounter_themes = self.get_property(TP_THEMES,[],{})
        theme_matched = 0
        for theme in encounter_themes:
          if theme in theme_prob_mults:
            prob = prob * theme_prob_mults[theme]
            theme_matched = 1
        if not theme_matched and (self.get_property(TP_IS_ENCOUNTER,0,{}) or self.get_property(TP_IS_GOOD_ENCOUNTER,0,{})):
          prob = prob * theme_prob_mults.get(E_OTHER,1)
      if properties_from_parent.get(TP_WANT_GOOD_ENCOUNTER,0) and not (self.get_property(TP_IS_GOOD_ENCOUNTER,0,{})):
        prob = prob / 2
      elif properties_from_parent.get(TP_WANT_ENCOUNTER,0) and not (self.get_property(TP_IS_ENCOUNTER,0,{}) or self.get_property(TP_IS_GOOD_ENCOUNTER,0,{})):
        prob = prob / 2             
      prob = prob * 2.0 / len(self.sockets)
      return prob

def place_encounter(template,inherited_properties,ready_room,subgrid,offset,group,good=0,no_monsters=0,no_terrains=0):
  # template: the template this encounter is being inserted in - use only for querying properties
  #            (or can be None, if being placed in a maze or similar)
  # inherited_properties: passed down from the parent template
  # ready_room: the ready_room this is being inserted in - use only for inserting objects or signpost messages (don't forget to apply offset)
  # subgrid: apply terrain changes here
  # offset: see above
  # group: add monsters here - again, don't forget offset 
  #    (or None if no_monsters is set)
  # good: flag
  if template is not None:
    terrain_chance = template.get_property(TP_TERRAIN_CHANCE,0.8,inherited_properties)
    terrain_veto_probs = template.get_property(TP_TERRAIN_VETO_PROBS,None,inherited_properties)
    fire_preference = template.get_property(TP_FIERY_PROB,1,inherited_properties)
  else:
    terrain_chance = inherited_properties.get(TP_TERRAIN_CHANCE,0.8)
    terrain_veto_probs = inherited_properties.get(TP_TERRAIN_VETO_PROBS,None)
    fire_preference = inherited_properties.get(TP_FIERY_PROB,1)
  if no_terrains==0 and random.random()<terrain_chance:
    # FIRST try for a terrain
    terrain_chosen = None
    max_n_of = 1
    if random.random()<=min(0.5,fire_preference-0.95):
      # lots of fire if a hot area
      terrain_chosen = '*'
      if template is None:
        max_n_of = random.randint(3,6)
      else:
        max_n_of = random.randint(5,max(8,template.width*template.height/8))     
    elif random.random()<=0.05:
      # fountain
      terrain_chosen = '!'
    elif random.random()<0.4:
      # trap
      terrain_chosen = random.choice((')','(','?','^'))
    elif random.random()<0.25:
      # multiple trap
      terrain_chosen = random.choice(('*','^'))
      max_n_of = random.randint(1,4)
    elif random.random()<0.3:
      # single scenery
      terrain_chosen = random.choice(('3','8','@'))
    elif random.random()<0.4:
      # multiple scenery
      terrain_chosen = random.choice(('7','9',':','&'))
      if template is None:
        max_n_of = random.randint(3,6)
      else:
        max_n_of = random.randint(3,max(6,template.width*template.height/16))
    no_fiery = 0
    no_wet = 0
    if template is not None:
      no_fiery = template.get_property(TP_FIERY_PROB,1,inherited_properties)<max(random.random(),0.1)
      no_wet = template.get_property(TP_WET_PROB,1,inherited_properties)<max(random.random(),0.1)
      wet = template.get_property(TP_WET,0,inherited_properties)
    else:
      no_fiery = inherited_properties.get(TP_FIERY_PROB,1)<max(random.random(),0.1)
      no_wet = inherited_properties.get(TP_WET_PROB,1)<max(random.random(),0.1)
      wet = inherited_properties.get(TP_WET,0)
    if terrain_chosen is not None and max_n_of>0 and not ((terrain_chosen=='*' and (wet or no_fiery)) or (terrain_chosen=='~' and no_wet)) and not (terrain_veto_probs is not None and random.random()<terrain_veto_probs.get(terrain_chosen,0)):
      requires_clear_space = 1
      requires_wall_with_adjacent_floor = 0
      if terrain_chosen == '&':
        requires_wall_with_adjacent_floor = 1 
        requires_clear_space = 0
      elif terrain_chosen in ('*',')','(','?','^','7','9','@'):
        requires_clear_space = 0
      terrain_locations = []
      tiles_drawn = []
      for i in range(max_n_of):
        random_tile = Grid_point(random.randint(0,subgrid.height-1),random.randint(0,subgrid.width-1))
        if random_tile in tiles_drawn:
          continue
        else:
          tiles_drawn.append(random_tile)
        contents = subgrid.get_cell(random_tile)
        ok = 0
        if requires_wall_with_adjacent_floor:
          if contents=='#':
            for i in range(-1,2):
              for j in range(-1,2):
                if (abs(i)+abs(j)==1):
                  this_tile = Grid_point(random_tile.down+i,random_tile.right+j)
                  if this_tile.down<subgrid.height and this_tile.right<subgrid.width and this_tile.down>=0 and this_tile.right>=0:
                    if subgrid.get_cell(this_tile)=='.':
                      ok = 1            
        elif contents=='.':
          ok = 1
          if requires_clear_space:
            for i in range(-1,2):
              for j in range(-1,2):
                this_tile = Grid_point(random_tile.down+i,random_tile.right+j)
                if this_tile.down<subgrid.height and this_tile.right<subgrid.width and this_tile.down>=0 and this_tile.right>=0:
                  if subgrid.get_cell(this_tile)<>'.':
                    ok = 0
        if ok:
          subgrid.set_cell(random_tile,terrain_chosen)
          ready_grid_location = Grid_point(random_tile.down+offset.down,random_tile.right+offset.right)
          ready_room.grid.set_cell(ready_grid_location,terrain_chosen) # one of these two will take, depending on when called
          offset_location = (random_tile.down+offset.down,random_tile.right+offset.right)
          if terrain_chosen=='@':
            message = random.choice(["Antoine was here",
                                     "You'll never find the Orb!",
                                     "No Adventurers Allowed",
                                     "Take heed: only a fool would go up against a fire-breathing dragon without an asbestos vest...",
                                     "Have you met the Dark Elf yet? You must defeat him to reach the Firedrake...",
                                     "If you're really in such a hurry to reach the Firedrake, go to the Crossroads...",
                                     "They say some rooms can never be teleported into...",
                                     "what does a potion of cure dianthroritis taste like?",
                                     "Never play leapfrog with a unicorn!",
                                     ])
            ready_room.signpost_messages[offset_location] = message      
  if template is not None:
    random_monster_chance = template.get_property(TP_RANDOM_MONSTER_CHANCE,1,inherited_properties)
  else:
    random_monster_chance = inherited_properties.get(TP_RANDOM_MONSTER_CHANCE,1)
  if not no_monsters and random.random()<random_monster_chance:
    # we'll try for some
    # well, for a test we'll try for a lone monster
    possibles_in_water = {} # M_:probability. These probs should be <=0.3 for tough encounters and >0.3 otherwise (see below)
    possible_small_groups_in_water = {} # M_:probability
    possible_large_groups_in_water = {} # M_:probability
    possibles_in_fire = {} # M_:probability
    possible_small_groups_in_fire = {} # M_:probability
    possible_large_groups_in_fire = {} # M_:probability
    possibles_in_floor = {} # M_:probability
    possible_small_groups_in_floor = {} # M_:probability
    possible_large_groups_in_floor = {} # M_:probability
    possible_led_groups_in_floor = {} # (M_,companion M_):probability
    difficulty = inherited_properties.get(TP_LEVEL_DIFFICULTY,1)
    for monster_info_key in mlib.m.keys():
      monster_info = mlib.m[monster_info_key]
      if monster_info.can_be_met_alone:
        if monster_info.level <= difficulty+1:
          if monster_info.level == difficulty+1:
            probability = 0.3
            led_probability = 0.1
          elif monster_info.level == difficulty:
            probability = 1
            led_probability = 0.3
          elif monster_info.level < difficulty-1:
            probability = 0.5
            led_probability = 0.5
          else:
            probability = 1
            led_probability = 1
          if template is None:
            theme_prob_mults = inherited_properties.get(TP_THEME_PROBS,None)
          else:
            theme_prob_mults = template.get_property(TP_THEME_PROBS,None,inherited_properties)
          if theme_prob_mults is not None:
            matched = 0
            for theme in monster_info.themes:
              if theme in theme_prob_mults:
                matched = 1
                probability = probability * theme_prob_mults[theme]
                led_probability = led_probability * theme_prob_mults[theme]
            if not matched:
              probability = probability * theme_prob_mults.get(E_OTHER,1)
              led_probability = led_probability * theme_prob_mults.get(E_OTHER,1)
          if monster_info.moves_through_flame_only:
            possibles_in_fire[monster_info_key] = probability
          elif monster_info.moves_through_water_only:
            possibles_in_water[monster_info_key] = probability
          else:
            possibles_in_floor[monster_info_key] = probability
            for companion in monster_info.can_be_met_with:
              possible_led_groups_in_floor[(monster_info_key,companion)] = led_probability
      if monster_info.can_be_met_in_groups:
        if monster_info.level <= difficulty:
          if monster_info.level == difficulty+1:
            small_group_probability = 0.3
            large_group_probability = 0.1
          elif monster_info.level == difficulty:
            small_group_probability = 1
            large_group_probability = 0.3
          elif monster_info.level == difficulty-3:
            small_group_probability = 0.5
            large_group_probability = 1
          elif monster_info.level <= difficulty-4:
            small_group_probability = 0.5
            large_group_probability = 0.5
          else:
            small_group_probability = 1
            large_group_probability = 1
          if template is None:
            theme_prob_mults = inherited_properties.get(TP_THEME_PROBS,None)
          else:
            theme_prob_mults = template.get_property(TP_THEME_PROBS,None,inherited_properties)
          if theme_prob_mults is not None:
            matched = 0
            for theme in monster_info.themes:
              if theme in theme_prob_mults:
                matched = 1
                small_group_probability = small_group_probability * theme_prob_mults[theme]
                large_group_probability = large_group_probability * theme_prob_mults[theme]
            if not matched:
              small_group_probability = small_group_probability * theme_prob_mults.get(E_OTHER,1)
              large_group_probability = large_group_probability * theme_prob_mults.get(E_OTHER,1)
          if monster_info.moves_through_flame_only:
            possible_small_groups_in_fire[monster_info_key] = small_group_probability
            possible_large_groups_in_fire[monster_info_key] = large_group_probability
          elif monster_info.moves_through_water_only:
            possible_small_groups_in_water[monster_info_key] = small_group_probability
            possible_large_groups_in_water[monster_info_key] = large_group_probability
          else:
            possible_small_groups_in_floor[monster_info_key] = small_group_probability
            possible_large_groups_in_floor[monster_info_key] = large_group_probability
    floor_random_tiles = []
    floor_offset_locations = []
    fire_random_tiles = []
    fire_offset_locations = []
    water_random_tiles = []
    water_offset_locations = []  
    tiles_drawn = []
    for i in range(10):
      random_tile = Grid_point(random.randint(0,subgrid.height-1),random.randint(0,subgrid.width-1))
      if random_tile in tiles_drawn:
        continue
      else:
        tiles_drawn.append(random_tile)
      offset_location = (random_tile.down+offset.down,random_tile.right+offset.right)
      contents = subgrid.get_cell(random_tile)
      if contents in ('.',','):
        floor_random_tiles.append(random_tile)
        floor_offset_locations.append(offset_location)
      elif contents in ('~'):
        water_random_tiles.append(random_tile)
        water_offset_locations.append(offset_location)
      elif contents in ('*'):
        fire_random_tiles.append(random_tile)
        fire_offset_locations.append(offset_location)
    large_group_size = random.randint(4,6)
    small_group_size = random.randint(2,3)
    if random.random()*10<=len(fire_random_tiles):
      random_tiles = fire_random_tiles
      offset_locations = fire_offset_locations
      options = possibles_in_fire
      small_group_options = possible_small_groups_in_fire
      large_group_options = possible_large_groups_in_fire
      led_group_options = {}
    elif random.random()*10<=len(water_random_tiles):
      random_tiles = water_random_tiles
      offset_locations = water_offset_locations
      options = possibles_in_water
      small_group_options = possible_small_groups_in_water
      large_group_options = possible_large_groups_in_water
      led_group_options = {}
    elif len(floor_random_tiles)>0:
      random_tiles = floor_random_tiles
      offset_locations = floor_offset_locations
      options = possibles_in_floor
      small_group_options = possible_small_groups_in_floor
      large_group_options = possible_large_groups_in_floor
      led_group_options = possible_led_groups_in_floor
    else:
      options = {}    
    if len(options.keys())>0:
      tries = 0
      while tries<10:
        tries = tries + 1
        if len(random_tiles)>=large_group_size and random.random()<0.3 and len(large_group_options.keys())>0:
          chosen_type = random.choice(large_group_options.keys())
          prob = large_group_options[chosen_type]
          if random.random() < prob:
            if prob<=0.3:
              good = 1
            tiles_to_use = random.sample(range(0,len(random_tiles)),large_group_size)
            for i in tiles_to_use:
              group.monster_types.append(chosen_type)
              group.locations.append(offset_locations[i])
            break
        if len(random_tiles)>=small_group_size and random.random()<0.5 and len(small_group_options.keys())>0:
          chosen_type = random.choice(small_group_options.keys())
          prob = small_group_options[chosen_type]
          if random.random() < prob:
            if prob<=0.3:
              good = 1
            tiles_to_use = random.sample(range(0,len(random_tiles)),small_group_size)
            for i in tiles_to_use:
              group.monster_types.append(chosen_type)
              group.locations.append(offset_locations[i])
            break
        if random.random()<0.3 and len(led_group_options.keys())>0:
          chosen_type_and_companion_type = random.choice(led_group_options.keys())
          prob = led_group_options[chosen_type_and_companion_type]
          if random.random() < prob:
            chosen_type = chosen_type_and_companion_type[0]
            companion_type = chosen_type_and_companion_type[1]
            i = random.choice(range(0,len(random_tiles)))
            leader_random_tile = random_tiles[i]
            leader_offset_location = offset_locations[i]
            possible_down_rights = []
            for down in range(-1,2):
              for right in range(-1,2):
                if down<>0 or right<>0:
                  if leader_random_tile.down+down<subgrid.height and leader_random_tile.right+right<subgrid.width and leader_random_tile.down+down>=0 and leader_random_tile.right+right>=0:
                    this_down_right = (down,right)
                    contents = subgrid.get_cell(Grid_point(leader_random_tile.down+down,leader_random_tile.right+right))
                    if contents=='.':
                      possible_down_rights.append(this_down_right)
            if len(possible_down_rights)>=large_group_size-1:
              if prob<=0.3:
                good = 1
              down_rights = random.sample(possible_down_rights,large_group_size-1)
              group.monster_types.append(chosen_type)
              group.locations.append(leader_offset_location)    
              for down_right in down_rights:
                group.monster_types.append(companion_type)
                group.locations.append((leader_offset_location[0]+down_right[0],leader_offset_location[1]+down_right[1]))   
              break
        if len(options.keys())>0:
          chosen_type = random.choice(options.keys())
          prob = options[chosen_type]
          if random.random() < prob:
            if prob<=0.3:
              good = 1
            for i in random.sample(range(0,len(random_tiles)),1):
              group.monster_types.append(chosen_type)
              group.locations.append(offset_locations[i])
            break        
  max_n_objects = 0
  if good:
    max_n_objects = 1
  if template is not None:
    loot_chance = template.get_property(TP_LOOT_CHANCE,0.4,inherited_properties)
  else:
    loot_chance = inherited_properties.get(TP_LOOT_CHANCE,0.4)
  while random.random()<loot_chance:
    max_n_objects = max_n_objects + 1
  if template is not None:
    difficulty = template.get_property(TP_LEVEL_DIFFICULTY,1,inherited_properties)
    allowed_slots = template.get_property(TP_ALLOWED_SLOTS,None,inherited_properties)
    allowed_items = template.get_property(TP_ALLOWED_ITEMS,None,inherited_properties)
  else:
    difficulty = inherited_properties.get(TP_LEVEL_DIFFICULTY,1)
    allowed_slots = inherited_properties.get(TP_ALLOWED_SLOTS,None)
    allowed_items = inherited_properties.get(TP_ALLOWED_ITEMS,None)
  possible_objects,possible_object_probs,possible_good_objects,possible_good_object_probs = get_object_tables(difficulty,allowed_slots,allowed_items)
  if len(possible_objects)>0 and max_n_objects>0:
    for i in range(max_n_objects):
      if i==0 and good:
        these_possible_objects = possible_good_objects
        these_possible_object_probs = possible_good_object_probs
      else:
        these_possible_objects = possible_objects
        these_possible_object_probs = possible_object_probs 
      if len(these_possible_objects)==0:
        continue
      done = 0
      count = 0
      while count<10 and not done:
        count = count + 1
        j = random.randint(0,len(these_possible_objects)-1)
        chosen_object = these_possible_objects[j]
        if random.random()<these_possible_object_probs[j]:
          random_tile = Grid_point(random.randint(0,subgrid.height-1),random.randint(0,subgrid.width-1))
          offset_location = (random_tile.down+offset.down,random_tile.right+offset.right)
          contents = subgrid.get_cell(random_tile)
          if contents in ('.',',','5','6','7','9','/'):
            if not offset_location in ready_room.objects:
              ready_room.objects[offset_location] = chosen_object
              done = 1


def get_object_tables(difficulty,allowed_slots,allowed_items):
  # either allowed_slots and allowed_items are both None, or they are [SL_] and [O_]
  possible_objects = []
  possible_object_probs = []
  possible_good_objects = []
  possible_good_object_probs = []
  for object in olib.o.keys():
    info = olib.o[object]
    if info.never_randomly_dropped or info.is_key:
      continue
    if allowed_slots is not None:
      if not (info.slot in allowed_slots or object in allowed_items):
        continue
    good_prob = 1
    prob = 1
    if info.common:
      pass
    elif info.rare:
      good_prob = good_prob * 0.2
      prob = prob * 0.1      
    else:
      good_prob = good_prob * 0.5
      prob = prob * 0.3
    if info.level <= difficulty+1:
      if info.level == difficulty+1:
        if info.quality:
          good_prob = good_prob * 0.05
          prob = 0
        else:
          good_prob = good_prob * 0.3
          prob = prob * 0
      elif info.level < difficulty-3 and not (info.quality or info.always_useful):
          good_prob = good_prob * 0.01
          prob = prob * 0.1
      elif info.level < difficulty-2 and not info.always_useful:
        if info.quality:
          good_prob = good_prob * 0.2
          prob = 0.4
        else:
          good_prob = good_prob * 0.05
          prob = prob * 0.2
      else:
        if info.quality:
          good_prob = good_prob * 1
          prob = 0.1
        else:
          good_prob = good_prob * 0.1
          prob = prob * 1        
    else:
      prob = 0
      good_prob = 0
    if good_prob>0:
      possible_good_objects.append(object)
      possible_good_object_probs.append(good_prob)
    if prob>0:
      possible_objects.append(object)
      possible_object_probs.append(prob)
  #print "creating object tables"
  #print "ordinary:"
  #for i in range(len(possible_objects)):
    #print olib.o[possible_objects[i]].name,possible_object_probs[i]
  #print "good:"
  #for i in range(len(possible_good_objects)):
    #print olib.o[possible_good_objects[i]].name,possible_good_object_probs[i]
  return possible_objects,possible_object_probs,possible_good_objects,possible_good_object_probs

def load_block_types(raw_block_types):
  # returns a dict where the key is (width,height) 
  # and the value is a list [sockets] where each 'sockets' is a [Grid_point]
  results = {}
  for raw_block in raw_block_types:
    buffer = text_block_to_list_of_strings(raw_block)
    grid = Grid(len(buffer[0])-2,len(buffer)-2)
    grid.read_bordered_grid(buffer,['+'],[])
    these_results_sockets = []
    for rotation in range(0,4):
      these_sockets = []
      for socket in grid.sockets:
        these_sockets.append(grid.rotate_point_clockwise(socket,rotation))
      these_sockets.sort()
      if not these_sockets in these_results_sockets:
        these_results_sockets.append(these_sockets)
        if rotation%2==0:
          this_width = grid.width
          this_height = grid.height
        else:
          this_width = grid.height
          this_height = grid.width 
        if not (this_width,this_height) in results:
          results[(this_width,this_height)] = []
        results[(this_width,this_height)].append(these_sockets)    
  return results

def classify_templates(basic_templates,templates_with_encounters,base_types):
  # return a dict where key is (width,height,n_sockets) and value is a dict,
  #               where key is a tuple of tupleised sockets and value is a [(template as Grid, rotation in quarters)].
  result = {}
  all_matches = 0
  for template in basic_templates+templates_with_encounters:
    template_matches = 0
    for rotation in range(0,4):
      if rotation%2==0:
        this_width = template.width
        this_height = template.height
      else:
        this_width = template.height
        this_height = template.width        
      candidate_socket_sets = base_types.get((this_width,this_height),[])
      if (len(candidate_socket_sets)>0):
        rotated_template_optional_socket_list = []
        rotated_template_definite_socket_list = []
        for i in range(len(template.sockets)):
          this_template_socket = template.sockets[i]
          if template.sockets_optional[i]:
            rotated_template_optional_socket_list.append(template.rotate_point_clockwise(this_template_socket,rotation))
          else:
            rotated_template_definite_socket_list.append(template.rotate_point_clockwise(this_template_socket,rotation))
        for candidate_socket_set in candidate_socket_sets:
          ok = 1
          for candidate_socket in candidate_socket_set:
            if not (candidate_socket in rotated_template_optional_socket_list) and not (candidate_socket in rotated_template_definite_socket_list):
              ok = 0
              break
          if ok:
            for socket in rotated_template_definite_socket_list:
              if not socket in candidate_socket_set:
                ok = 0
                break
          if ok:
            key1 = (this_width,this_height,len(candidate_socket_set))
            if not key1 in result:
              result[key1] = {}
            key2 = []
            for socket in candidate_socket_set:
              key2.append(socket.to_tuple())
            key2.sort()
            key2 = tuple(key2)
            if not key2 in result[key1]:
              result[key1][key2] = []
            result[key1][key2].append((template,rotation))
            template_matches = template_matches + 1
            all_matches = all_matches + 1
    if template_matches==0:
      print "No matches for this template: "
      print template
      print '\n\n'
  return result

class Special_grid:
  def __init__(self,terrain='.',monster=None,random_good_object=0,random_object=0,object=None,signpost_message='',exit_to=None,monster_probability=1,object_probability=1):
    self.terrain = terrain
    self.monster = monster
    self.random_object = random_object
    self.random_good_object = random_good_object
    self.object = object
    self.signpost_message = signpost_message
    self.exit_to = exit_to # (a 2-tuple, with first element a D_ code, second element ignored - unless first element is D_MAIN_DUNGEON, in which case second element is a difficulty level)
    self.monster_probability = monster_probability # ignored if monster=None
    self.object_probability = object_probability # ignored if monster=None

class Ready_group:
  # members include:
  # monster_types - [M_] 
  # attitude - A_FRIENDLY, A_NEUTRAL or A_HOSTILE
  # locations - [(down,right)]
  # TO DO - allow a specification of which groups are enemies here - A bit tricky as cannot use group ids - not defined yet. Oh well, implement it when you need it...
  pass

class Possible_message:
  def __init__(self,prob,message,sound,volume=1):
    self.prob = prob # a probability
    self.message = message # a string to print
    self.sound = sound # name of a wav
    self.volume = volume
    
psyco.bind(Grid_point.__init__)   
psyco.bind(Grid_point.point_in_dir)
psyco.bind(Grid.__init__)
psyco.bind(Grid.has_any)
psyco.bind(Grid.valid)
psyco.bind(Grid.fill)
psyco.bind(Grid.blit)
psyco.bind(Grid.fill_with_maze)
psyco.bind(Grid.stipple_with_blocks)
psyco.bind(Grid.rotate_clockwise)
psyco.bind(Grid.rotate_point_clockwise)
psyco.bind(Grid.lrflip)
psyco.bind(Grid.udflip)
psyco.bind(load_bordered_grids)
psyco.bind(Grid.read_bordered_grid)
psyco.bind(classify_templates)
psyco.bind(Template.apply)
psyco.bind(Template.__init__)
psyco.bind(Template.get_property)
psyco.bind(Template.convert_lowercase_letter)
psyco.bind(load_block_types)
psyco.bind(place_encounter)
psyco.bind(get_object_tables)

